/** 
 * Author: Andrew Shore
 * Date Last Modified: April 10, 2009
 * CSCE 146: Homework 06, BST.java
 * 
 * Description:
 * This class implements a Binary Search Tree of Binary Tree nodes. The search tree
 * is used to sort Record objects. The binary search tree contains a root node such 
 * that all elements in the left subtree of the node are less than the root and all
 * elements in the right subtree are greater than the root. Each node in the tree is
 * also a binary search tree.
 */
public class BST implements IBST {
	
	/**
	 * Instance variables
	 */
	BTNode root;
	int size;
	int totalHeight;
	private static final int arraySize = 2000;
	//writeHistory[] - array that stores the frequency of nodes at a given height
	private int[] writeHistory;
	private static final String classLabel = "BST:	";
	int maxHeight = 0;
	
	/**
	 * Default constructor
	 */
	public BST(){
		writeHistory = new int[arraySize];
		size = 0;
	}
	
	/**
	 * Accessors
	 */

	public BTNode getRoot() {
		return root;
	}
	
	public int getSize() {
		return size;
	}
	
	public int getTotalHeight() {
		return totalHeight;
	}

	public int getNodeCount() {
		return size;
	}
	/**
	 * Mutators
	 */
	public void setRoot(BTNode v) {
		if(v == null){
			throw new NullPointerException();
		}
		root = v;
	}

	public void setSize(int what) {
		size = what;
	}
	
	/**
	 * Adds a node at the root of the tree
	 * 
	 * Parameters: v - node to be added to the tree
	 */
	public BTNode addRoot(BTNode v) {
		if(v == null){
			throw new NullPointerException();
		}
		else{
			root = v;
			writeHistory[0]++;
			size++;
		}
		
		return root;
	}

	/**
	 * Method returns true if the testString is found in the Record of a 
	 * node in the tree
	 * 
	 * Parameters: testString - string to be searched in the records of the 
	 *                           binary search tree
	 */
	public boolean contains(String testString) {
		boolean notFound = true;
		int numberOfProbes = 0;
		
		BTNode currentNode = root;		//cursor to iterate through the tree
		
		Record testRecord = new Record(testString);
		BTNode testNode = new BTNode();
		
		testNode.setElement(testRecord);
		
		while(notFound){
			numberOfProbes++;
			//if the string is less than the the current node then we look in the left subtree
			if(testNode.compareTo(currentNode) < 0){
				//if the node has a left child we increment currentNode to the child's position
				if(currentNode.hasLeft()){
					currentNode = currentNode.getLeft();
				}
				//if the node does not have a child we know that the string is not in the tree
				else{
					notFound = false;
				}	
			}
			//same as the first if statement but we look into the right subtree if the
			//node is greater than the current node
			else if(testNode.compareTo(currentNode) > 0){
				if(currentNode.hasRight()){
					currentNode = currentNode.getRight();
				}
				else{	
					notFound = false;
				}
				
			}
			else{
				FileUtils.logFile.println(classLabel + " leave 'contains' after " + 
			   			                   numberOfProbes + " probes");
				return true;
			}
			
			
		}//while(notFound)
		FileUtils.logFile.println(classLabel + " leave 'contains' after " + 
				                   numberOfProbes + " probes");
		return false;
	}
	
	/**
	 * Searches the binary search tree for searchNode and returns true if it
	 * is found. Very similar to the contains method above but searches for a 
	 * node, not a string.
	 * 
	 * Parameters: searchNode - node to be searched for in the binary search tree
	 */
	public boolean containsNode(BTNode searchNode){
		boolean notFound = true;
		BTNode currentNode = root; 	//cursor to iterate through the tree
		

		
		while(notFound){
			
			//if the string is less than the the current node then we look in the left subtree
			if(searchNode.compareTo(currentNode) < 0){
				//if the node has a left child we increment currentNode to the child's position
				if(currentNode.hasLeft()){
					currentNode = currentNode.getLeft();
				}
				//if the node does not have a child we know that the string is not in the tree
				else{
					notFound = false;
				}	
			}
			//same as the first if statement but we look into the right subtree if
			//the node is greater than the current node
			else if(searchNode.compareTo(currentNode) > 0){
				if(currentNode.hasRight()){
					currentNode = currentNode.getRight();
				}
				else{	
					notFound = false;
				}
				
			}
			else{
				return true;
			}
			
			
		}//while(notFound)
		return false;
	}
	
	/**
	 * Creates a node from the given parameters and returns it
	 * 
	 * Parameters: rec - Record of the new node being created
	 * 			   parent - parent node of node being created
	 *             left - left child of node being created
	 *             right - right child of node being created
	 */
	public BTNode createNode(Record rec, BTNode parent, BTNode left,BTNode right) {
		BTNode theNode = new BTNode(rec, parent, left, right);
		return theNode;
	}


	/**
	 * Inserts a node into the tree making sure the binary search tree properties hold
	 * 
	 * Parameters: insertNode - node being added to the tree
	 */
	public BTNode insert(BTNode insertNode) {
		if(insertNode == null){
			throw new NullPointerException();
		}
		//if there is no root we add the record to the root of the tree
		if(root == null){
			this.addRoot(insertNode);
		}
		else{
			//we don't allow duplicates so if it already contains the record we don't add it
			if(!this.containsNode(insertNode)){
				boolean notSorted = true;
				BTNode currentNode = root;	 	//cursor to iterate through the tree
			
				while(notSorted){
				
				//if the record is less than the cursor we look into the left subtree 
					if(insertNode.compareTo(currentNode) <= 0){
						//if it has a left child we move cursor to that position
						if(currentNode.hasLeft()){
							currentNode = currentNode.getLeft();
						}
						/*if it does not have a child then we add it as the left child 
						 * and increment appropriate attributes
						*/
						else{
							currentNode.setLeft(insertNode);
							insertNode.setParent(currentNode);
							notSorted = false;
							size++;
							totalHeight += insertNode.getHeight();
							writeHistory[insertNode.getHeight()]++;
						}	
					}
					//same as above except we look into the right subtree
					else if(insertNode.getElement().compareTo(currentNode.getElement()) > 0){
						if(currentNode.hasRight()){
							currentNode = currentNode.getRight();
						}
						else{
							currentNode.setRight(insertNode);
							insertNode.setParent(currentNode);
							notSorted = false;
							size++;
							totalHeight += insertNode.getHeight();
							writeHistory[insertNode.getHeight()]++;
						}	
					
					}
					 
				}//while(notSorted)
			}
		}
			return insertNode;
	}
	
	/**
	 * Method returns true if empty, else false
	 */
	public boolean isEmpty() {
		return (this.size == 0);
	}

	/**
	 * Method returns true if the given node is the root of the 
	 * tree(meaning the node does not have a parent)
	 * 
	 * Parameters: v - node being checked if its the root of the tree
	 */
	public boolean isRoot(BTNode v) {
		if(v == null){
			throw new NullPointerException();
		}
		if(v.getParent() != null){
			return false;
		}
		else{
			return true;
		}
		
	}

	/**
	 * Method traverses the tree in an inorder fashion and returns a string
	 * of the ordered tree
	 * 
	 * Parameters: v - node that marks the start of the inorder traversal
	 */
	public String toStringInorder(BTNode v) {
		if(v == null){
			throw new NullPointerException();
		}
		String s = "";
		
		//recursively calls method for left subtree
		if(v.hasLeft()){
			s += toStringInorder(v.getLeft());
		}
		
		s += "\n";
		
		//adds current node information to the string
		if(v.getHeight() > maxHeight){
			maxHeight = v.getHeight();
			FileUtils.logFile.println(classLabel + " new maxHeight:	" + maxHeight);
		}
		s += "	" + v.getElement().toString() + ":	" + v.getHeight() + "	";
		
		//recursively calls method for right subtree
		if(v.hasRight()){
			s += toStringInorder(v.getRight());
		}	
		
		return s;
	}


	/**
	 * Prints out the array of the number of nodes at each height
	 */
	public void writeHeightHisto() {
		
		for(int i = 0; i < writeHistory.length; i++){
			FileUtils.logFile.println(classLabel + "heightHisto[" + i + "] =		" 
					                   + writeHistory[i]);
		}
		
	}

}
